Colour-and-forward: relaying “what the destination needs” in the zero-error primitive relay channel

Abstract — Zero-error communication over a primitive relay channel is for the first time proposed and studied. This model is used to highlight how one may exploit the channel structure to design a relaying strategy that explicitly provides “what destination needs”. We propose the Colour-and-Forward relaying scheme which constructs a graph GR of relay outputs based on the joint conditional distribution of the relay and destination outputs given the channel input. The colours of this graph GR are sent over the out-of-band link in the primitive relay channel and are shown to be information lossless in the zero-error sense; they result in the same confusability graph as if the destination had the relay’s received signal. This allows us to obtain an upper bound1 on the minimum required conference rate required for the relay and destination terminals to be effectively fully cooperative for any number of channel use n